package com.atguigui.leetcode1;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 1851. 包含每个查询的最小区间
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/7/18 9:42
 */
public class P1851MinimumIntervalToIncludeEachQuery {
    public static void main(String[] args) {

    }

    class Solution {
        public int[] minInterval(int[][] intervals, int[] queries) {
            // 将所有数组按照第一个元素进行排序
            Arrays.sort(intervals, ((o1, o2) -> o1[0] - o2[0]));

            // 将查询结果放入数组中，并指定下标
            int[][] que = new int[queries.length][2];
            for (int i = 0; i < queries.length; i++) {
                que[i][0] = queries[i];
                que[i][1] = i;
            }
            // 按照查询内容大小进行排序
            Arrays.sort(que, (o1, o2) -> o1[0] - o2[0]);

            int[] res = new int[queries.length];
            Arrays.fill(res, -1);
            // 优先队列
            PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o1[0] - o2[1] + o2[0]);

            int index = 0;
            for (int i = 0; i < queries.length; i++) {
                while (index < intervals.length && que[i][0] >= intervals[index][0]) {
                    queue.offer(new int[]{intervals[index][0], intervals[index][1]});
                    index++;
                }
                while (!queue.isEmpty() && queue.peek()[1] < que[i][0]) {
                    queue.poll();
                }

                if (!queue.isEmpty()) {
                    int[] t = queue.peek();
                    res[que[i][1]] = t[1] - t[0] + 1;
                }
            }


            return res;
        }
    }
}
